#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    unordered_map<int, int> hash;
    int getKth(int lo, int hi, int k) {
        hash[1] = 0;
        vector<int> vv(hi - lo + 1);
        for (int i = lo; i <= hi; ++i)
        {
            vv[i - lo] = i;
            dfs(i);
        }
        sort(vv.begin(), vv.end(), [&](const int& x, const int& y) {
            if (hash[x] < hash[y])
                return true;
            if (hash[x] == hash[y])
                return x < y;
            return false;
            });

        return vv[k - 1];
    }

    int dfs(int x)
    {
        if (hash.count(x))
        {
            return hash[x];
        }

        int tmp = 0;
        if (x % 2 == 1)
        {
            tmp = 1 + dfs(x * 3 + 1);
        }
        else
        {
            tmp = 1 + dfs(x / 2);
        }
        hash[x] = tmp;

        return hash[x];
    }
};